package algorithm.h23d_p17;
//2.一个机器人位于一个 m x n 网格的左上角，网格中存在 k 个障碍物位于[ik，jk],机器人
// 每次只能向下或者向右移动一步，机器人试图达到网格的右下角，请打印出最短的可行的移动路径

//问题：如果有路径的话 那么路径值应该是固定的啊？何来最短一说？
//问题：障碍物数量没有确定的情况下，机器人是否可达确实存在问题

//重述，该类用于确定是否存在可达路径，以及输出可达路径图和一个可达路径案例
//input：二维数组 0为障碍物（终点和起点会被重新设置为1，不能终点和起点为0）
//打印：可达路径图 0为障碍物 1 为可选路径 -1 为不可选路径
//打印: 可达路径案例 如果可达，打印一条路径，否则打印"不存在路径"
import java.util.Arrays;

public class FindRobotPath {
//    输入一个二维数组，0代表障碍物，1代表候选可行路径
    /**
     *
     * @param matrix 输入的二维数组
     * @return 返回表示机器人路径的二维数组，如果不可达，返回空数组
     */
    private static int [][] FindRobotPaths(int[][] matrix){
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[][]{};
        }
//        int [][] path=new int[matrix.length][matrix[0].length];
        int rowsLength=matrix.length;
        int colsLength=matrix[0].length;
        //        需要获取坐标，不使用matrix.for遍历
//        倒序遍历 以0为障碍物 扩展 -1位置不可达（如果到达坐标值为-1的位置就必定无法到达终点）
        for (int i = rowsLength-1; i >=0 ; i--) {
            for (int j = colsLength-1; j >=0; j--) {
                updateMatrix(matrix,i,j);
            }
        }
//        正序遍历，扩展不可达位置
        for (int i = 0; i < rowsLength; i++) {
            for (int j = 0; j < colsLength; j++) {
                updateMatrixPlus(matrix,i,j);

            }

        }
        return matrix;

    }

    private static void updateMatrixPlus(int[][] matrix, int row, int col) {
        //        1. 如果是起点和终点左边固定值为1 也就是相当于不修改
        if (row==0&&col==0) {
            matrix[0][0]=1;
            return;
        }
        if (row==matrix.length-1&&col==matrix[0].length-1) {
            matrix[row][col]=1;
            return;
        }
//        2. 如果当前值为0 不修改
        if (matrix[row][col]==0)
            return;
        //        3.2 左侧和上方值不为1：或者不存在左侧值和上方值: 这个需要正序遍历
        if ((row-1==-1||matrix[row-1][col]!=1)&&(col-1==-1||matrix[row][col-1]!=1)){
            matrix[row][col]=-1;
            return;
        }
    }

    private static void updateMatrix(int[][] matrix,int row,int col) {
//        1. 如果是起点和终点左边固定值为1 也就是相当于不修改
        if (row==0&&col==0) {
            matrix[0][0]=1;
            return;
        }
        if (row==matrix.length-1&&col==matrix[0].length-1) {
            matrix[row][col]=1;
            return;
        }
//        2. 如果当前值为0 不修改
        if (matrix[row][col]==0)
            return;

//        3. 如果当前值不为0,就说明当前值为1，检测障碍物情况更新为-1
//        3.1 右侧与下方值不为1：（下方不存在值 或者下方值不为1）并且(右侧不存在值 或者 右侧值不为1）
        if ((row+1==matrix.length||matrix[row+1][col]!=1)&&(col+1==matrix[0].length||matrix[row][col+1]!=1)){
            matrix[row][col]=-1;
            return;
        }

//        3.2 左侧和上方值不为1：或者不存在左侧值和上方值: 这个需要正序遍历 以在updateMatrixPlus中实现
//        if ((row-1==-1||matrix[row-1][col]!=1)&&(col-1==-1||matrix[row][col-1]!=1)){
//            matrix[row][col]=-1;
//            return;
//        }
    }
//    打印二维矩阵
    private static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }

    /**
     * 非空二维数组
     * @param matrix
     */
    private static void FindRobotOnePath(int[][] matrix) {
//        遍历矩阵 跟着1走
        int i=0,j=0;
        int rows=matrix.length,cols=matrix[0].length;
        int [][]path=new int[rows][cols];
        path[0][0]=1;
        while (true){
            if (j+1<cols&&matrix[i][j+1]==1){
                j++;
                path[i][j]=1;
                continue;
            }
            if (i+1<rows&&matrix[i+1][j]==1){
                i++;
                path[i][j]=1;
                continue;
            }
            break;

        }
        if (path[rows-1][cols-1]==0)
            System.out.println("不存在路径");
        else printMatrix(path);

    }

    public static void run(int[][] matrix) {
//        int[][] matrix = {
//                {1, 1, 1, 1},
//                {0, 1, 0, 1},
//                {0, 1, 0, 1}
//
//        };
        matrix=FindRobotPaths(matrix);

        System.out.println("路径图为:");
        printMatrix(matrix);
        if (matrix.length==0)
            System.out.println("矩阵为空");
        else{
            System.out.println("机器人路径为:");
            FindRobotOnePath(matrix);}
    }


}
